#include "./min_span_tree.h"

void prim(MGraph &graph)
{
	// 初始化辅助数组
	// 辅助数组的意义：比如说adjvex[1]=0表示找到了顶点0开始到顶点1终止构成的最短边，其最短边长度为lowcost[1]
	int adjvex[graph.vexNum];  // 保存相关顶点间边的权值点下标
	int lowcost[graph.vexNum]; // 保存相关顶点间的权值
	// 把顶点0加入最小生成树
	adjvex[0] = 0;
	// lowcost为0表示这个点已被加入最小生成树
	lowcost[0] = 0;
	for (int i = 1; i < graph.vexNum; i++)
	{
		// adjvex全初始化为0表示都先从顶点0开始
		adjvex[i] = 0;
		lowcost[i] = graph.edge[0][i];
	}
	int min, current; // 分别表示当前找到的最小边长度和当前最小边的点的下标
	for (int i = 1; i < graph.vexNum; i++)
	{
		min = INFINITY;
		current = 0;
		// 循环全部顶点
		for (int j = 1; j < graph.vexNum; j++)
		{
			if (lowcost[j] != 0 && lowcost[j] < min)
			{
				min = lowcost[j];
				current = j;
			}
		}
		cout << "(" << adjvex[current] << ", " << lowcost[current] << ")" << endl;
		lowcost[current] = 0; // 表示当前找到的最小路径对应的点已被加入最小生成树
		// 循环所有顶点
		for (int j = 1; j < graph.vexNum; j++)
		{
			// 当前点的各边权值小于此前这些顶点未被加入的生成树权值
			if (lowcost[j] != 0 && graph.edge[current][j] < lowcost[j])
			{
				lowcost[j] = graph.edge[current][j];
				adjvex[j] = current;
			}
		}
	}
}